package fun.coding.leetcode;

import java.util.Stack;

public class LongestValidParentheses {

	public static void main(String[] args) {
		LongestValidParentheses ins = new LongestValidParentheses();
		System.out.println(ins.longestValidParentheses("(()"));
		System.out.println(ins.longestValidParentheses("((()))"));
		System.out.println(ins.longestValidParentheses(")()())"));
		// This means using stack counting not working, below returns ()
		System.out.println(ins.longestValidParentheses("()(()"));
	}
	
	// http://fmarss.blogspot.com/2014/09/leetcode-solution-longest-valid.html
	public int longestValidParentheses(String s) {
		if (s == null || s.length() <= 1) return 0;
		
		Stack<Character> stack = new Stack<Character>();
		
		int max = 0;
		int cur = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(') {
				stack.push('(');
			} else {
				if (stack.isEmpty()) {
					cur = 0;
				} else {
					stack.pop();
					cur++;
				}
			}
			max = Math.max(max, cur);
		}
		return max * 2;
	}

}
